#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

class Solution:
    def magicalString(self, n: int) -> int:
        if n < 4:
            return 1

        s = [0 for _ in range(2 * n)]
        res = 1
        s[0] = 1
        s[1] = 2
        s[2] = 2

        j = 3
        for i in range(2, n):
            if s[i] == 1:
                res += 1
                s[j] = 2 if s[j - 1] == 1 else 1
                j += 1
            else:
                s[j] = 2 if s[j - 1] == 1 else 1
                s[j + 1] = s[j]
                j += 2

        return res
